package com.ken.algorithms.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

/**
 * <ul>
 * <li>Title: CD174_LC98Main</li>
 * <li>Description:
 *      NowCoder：CD174. 判断一棵二叉树是否为搜索二叉树和完全二叉树
 *      LeetCode：98. 验证二叉搜索树 — Medium
 * </li>
 * </ul>
 *
 * @author swc
 * @date 2021-09-10 15:40
 */

//给定一棵二叉树，已经其中没有重复值的节点，请判断该二叉树是否为搜索二叉树和完全二叉树。


/*第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)
ps:节点的标号就是节点的值*/
public class CD174_LC98Main {

    //判断搜索二叉树 isBST：根据搜索二叉树的中序遍历的结果是升序的这一特点，如果出现降序或者相等，就直接返回 false
    public static void main(String[] args) {
        /*3 2
2 1 3
1 0 0
3 0 0*/

        /*
8 10 9
10 5 12
5 0 0
12 0 0
9 0 3
3 0 0
        * */


                /*
8 10 9
10 5 0
5 0 0
9 0 3
3 0 0
        * */

        Scanner scanner = new Scanner(System.in);
        System.out.println("输入节点总数和根节点总数:");
        String next = scanner.nextLine();//其实这个没什么意义
        TreeNode treeNode = TreeUtil.createTreeNode(scanner);


        boolean bst = isBST(treeNode);

        System.out.println(bst);

    }

    private static boolean isBST(TreeNode root) {

        if(root==null || root.getVal()==0){
            return false;
        }

        Stack<TreeNode> stack = new Stack<>(); // 辅助栈
        TreeNode cur = root; // 工作指针



        TreeNode pre = null; // 中序遍历的前驱节点
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                if (!stack.isEmpty() && stack.peek().getVal() <= cur.getVal() ) {
                    return false;
                }
                stack.push(cur);
                cur = cur.getLeft();
            }
            else {
                cur = stack.pop();
                if (pre != null && pre.getVal() >= cur.getVal() ) {
                    return false;
                }
                pre = cur;
                cur = cur.getRight();
                //System.out.println(pre.getVal());
            }
        }
        return true;
    }

}
